class Solution(object):
    def findRadius(self, houses, heaters):
        """
        :type houses: List[int]
        :type heaters: List[int]
        :rtype: int
        """
        def possible(houses, heaters, r):
            start = houses[0]
            for i in heaters:
                if i - r > start:
                    return False
                #最远可覆盖到哪个房间
                idx = bisect.bisect_right(houses, i + r)
                if idx >= len(houses):
                    return True
                start = houses[idx]
            return False


        houses = sorted(houses)
        heaters = sorted(heaters)
        l = 0
        #供暖器放的位置也需要考虑
        r = max(houses[-1], max(heaters)) - 1
        while l <= r:
            mid = (l + r) >> 1
            if not possible(houses, heaters, mid):
                l = mid + 1
            else:
                r = mid - 1
        return l
